#include <linux/xarray.h>
#include <linux/stdlib.h>

/**
 * xa_load() - Load an entry from an XArray.
 * @xa: XArray.
 * @index: index into array.
 *
 * Context: Any context.  Takes and releases the RCU lock.
 * Return: The entry at @index in @xa.
 */
void *xa_load(struct xarray *xa, xa_key_t index)
{
    void *entry;

    return entry;
}

static inline xa_key_t xa_mk_index_start(xa_key_t index)
{
    return index & ~(XA_CHUNK_MASK);
}

static int xa_alloc_node(struct xarray *xa, xa_key_t index, void *entry,
                         gfp_t gfp, struct xa_node **node)
{
    struct xa_node *n;
    int pos;
    int error = 0;

    n = kzalloc(sizeof(struct xa_node), gfp);
    if (n)
    {
        pos = index & XA_CHUNK_MASK;
        n->index_start = xa_mk_index_start(index);
        n->slots[pos] = entry;
        __set_bit(pos, n->slots_used);
    }
    else
    {
        error = -ENOMEM;
    }

    *node = n;

    return error;
}

static void __xa_add(struct xarray *xa, struct xa_node *parent, struct xa_node *node)
{
    xa_key_t offset = node->index_start - parent->index_start;

    offset = offset & XA_CHUNK_MASK;
    node->prev_entry = parent->slots[offset];
    parent->slots[offset] = node;
    __set_bit(offset, parent->is_node);
    if (xa->xa_head == node)
        xa->xa_head = parent;
}

int __xa_store(struct xarray *xa, xa_key_t index, void *entry, gfp_t gfp, xa_entry_t *old)
{
    struct xa_node *node;
    xa_key_t index_start;
    int error = 0;

    node = xa->xa_head;
    if (!node)
    {
        error = xa_alloc_node(xa, index, entry, gfp, &node);

        xa->xa_head = node;
    }
    else
    {
        index_start = xa_mk_index_start(index);

        if (index_start == node->index_start)
        {
            int pos = index & XA_CHUNK_MASK;

            node->slots[pos] = entry;
        }
        else if (index_start < node->index_start)
        {
            struct xa_node *node_new;

            error = xa_alloc_node(xa, index, entry, gfp, &node_new);
            if (error == 0)
            {
                __xa_add(xa, node_new, node);
            }
        }
        else if (index_start > node->index_start)
        {
            struct xa_node *node_new;

            error = xa_alloc_node(xa, index, entry, gfp, &node_new);
            if (error == 0)
            {
                __xa_add(xa, node, node_new);
            }
        }
    }

    return error;
}

void *xa_store(struct xarray *xa, xa_key_t index, void *entry, gfp_t gfp)
{
    void *curr;

    __xa_store(xa, index, entry, gfp, &curr);

    return curr;
}
